package com.lh.leetcodetop100.查找;

/**
 * @author: linghao
 * @since: 2022/7/31
 */
public class 二分查找 {

    /**
     * 最简单的二分查找，不能包含重复数字
     * O(logn)
     */
    public static int simpleBsearch(int[] a,int val){
        if(null == a || a.length<=0)return -1;
        int low = 0,high = a.length-1;
        while(low<=high){
            int mid = low+((high-low)>>1);  //效果等价 （low+high）/2,但是low 和 high 比较大的话，两者之和就有可能会溢出
            if(a[mid] > val){
                high = mid - 1;     //这里加1 减1 是为了防止相等时的死循环，比如，当 high=3，low=3 时，如果 a[3]不等于 value，就会导致一直循环不退出
            }else if(a[mid] < val){
                low = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

    /**
     * 二分查找变种1：查找第一个值等于给定值得元素
     * 允许有重复元素
     */
    public static int bSearchFirst(int[] a,int val){
        if(null == a || a.length<=0)return -1;
        int low = 0,high = a.length - 1;
        while(low<=high){
            int mid = low+((high-low)>>1);
            if(a[mid] >= val){
                high = mid - 1;
            }else if (a[mid] < val){
                low = mid + 1;
            }
        }

        if(low < a.length && a[low] == val){
            return low;
        }else{
            return -1;
        }
    }


    /**
     * 二分查找变种2：查找最后一个值等于给定值得元素
     */
    public static int bSearchLast(int[] a,int val){
        if(null == a || a.length<=0)return -1;
        int low = 0,high = a.length - 1;
        while(low<=high){
            int mid = low+((high - low)>>1);
            if(a[mid] > val){
                high = mid -1;
            }else if(a[mid] <= val){
                low = mid +1;
            }
        }
        if(high > 0 && a[high] ==val){
            return high;
        }else{
            return -1;
        }
    }
    /**
     * 二分查找变种3：查找第一个大于等于给定值得元素
     */
    public static int bSearchLeFirst(int[] a,int val){
        if(null == a || a.length<=0)return -1;
        int low = 0,high = a.length - 1;
        while(low<=high){
            int mid = low+((high-low)>>1);
            if(a[mid] >= val){
                if(mid == 0||a[mid-1]<val){
                    return mid;
                }else{
                    high = mid -1;
                }
            }else{
                low = mid +1;
            }
        }
        return -1;
    }
    /**
     * 二分查找变种4：查找最后一个小于等于给定值得元素
     */
    public static int bSearchLelast(int[] a,int val){
        if(null == a || a.length<=0)return -1;
        int low = 0,high = a.length - 1;
        while(low<=high){
            int mid = low+((high - low)>>1);
            if(a[mid] <= val){
                if(mid == high||a[mid+1]>val){
                    return mid;
                }else{
                    low = mid +1;
                }
            }else{
                high = mid - 1;
            }
        }
        return -1;
    }



    public static void main(String[] args) {
        int[] test = {1,1,3,4,5,6,6,6,7,87,89,98,98};
//        int[] test = {5,6,6,6};
//        System.out.println(simpleBsearch(test,87));
//        System.out.println(bSearchFirst(test,6));
//        System.out.println(bSearchLast(test,1));
//        System.out.println(bSearchLeFirst(test,2));
        System.out.println(bSearchLelast(test,6));
    }
}
